package com.lin.codesnippet.treeNome;


import lombok.Data;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 普通二叉树
 *
 * @author linqiankun
 */
public class Tree<T> {

    /**
     * 递归实现前序遍历
     *
     * @param node 跟节点
     */
    public void preOrderTraverse(Node<T> node) {
        if (node != null) {
            System.out.println(node.getValue());
            preOrderTraverse(node.getLeft());
            preOrderTraverse(node.getRight());
        }
    }

    /**
     * 非递归实现的前序遍历
     *
     * @param root 跟节点
     */
    public void nrPreOrderTraverse(Node<T> root) {
        //借助栈实现
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Node<T> node = root;
        while (node != null || !stack.isEmpty()) {

            while (node != null) {
                System.out.println(node.getValue());
                stack.push(node);
                node = node.getLeft();
            }
            node = stack.pop();
            node = node.getRight();
        }

    }

    /**
     * 递归实现的中序遍历
     *
     * @param node 跟节点
     */
    public void inOrderTraverse(Node<T> node) {
        if (node != null) {
            inOrderTraverse(node.getLeft());
            System.out.println(node.getValue());
            inOrderTraverse(node.getRight());
        }
    }

    /**
     * 非递归实现的中序遍历
     *
     * @param root 跟节点
     */
    public void nrInOrderTraverse(Node<T> root) {
        Stack<Node<T>> stack = new Stack<Node<T>>();
        Node<T> node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }
            node = stack.pop();
            System.out.println(node.getValue());
            node = node.getRight();
        }
    }

    /**
     * 递归实现的后续遍历
     *
     * @param node 跟节点
     */
    public void postOrderTraverse(Node<T> node) {
        if (node != null) {
            postOrderTraverse(node.getLeft());
            postOrderTraverse(node.getRight());
            System.out.println(node.getValue());
        }
    }

    /**
     * 非递归实现的后续遍历
     *
     * @param root 跟节点
     */
    public void nrPostOrderTraverse(Node<T> root) {

        Stack<Node<T>> stack = new Stack<Node<T>>();
        Node<T> node = root;
        //表示最近一次访问的节点
        Node<T> preNode = null;

        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }

            node = stack.peek();

            if (node.getRight() == null || node.getRight() == preNode) {
                System.out.println(node.getValue());
                node = stack.pop();
                preNode = node;
                node = null;
            } else {
                node = node.getRight();
            }
        }
    }

    /**
     * 借助队列实现的层序遍历
     *
     * @param node 跟节点
     */
    public void levelTraverse(Node<T> node) {
        //借助队列实现
        Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
        queue.add(node);
        while (!queue.isEmpty()) {

            Node<T> temp = queue.poll();
            if (temp != null) {
                System.out.println(temp.getValue());
                queue.add(temp.getLeft());
                queue.add(temp.getRight());
            }
        }
    }

    /**
     * 获取树的深度
     *
     * @param node 跟节点
     * @return 树的深度
     */
    private Integer getHeight(Node node) {
        if (node == null) {
            return 0;
        } else {
            int left = getHeight(node.getLeft());
            int right = getHeight(node.getRight());
            //左子树 右子树最深的，再加上父节点本身深度1
            return left > right ? left + 1 : right + 1;
        }
    }

    /**
     * 获取节点数量
     *
     * @param node 跟节点
     * @return 节点数量
     */
    private Integer getSize(Node node) {
        if (node == null) {
            return 0;
        } else {
            int leftSize = getSize(node.getLeft());
            int rightSize = getSize(node.getRight());
            return leftSize + rightSize + 1;
        }
    }


    @Data
    public class Node<T> {
        Node left;
        Node right;
        T value;
    }


}
